package com.jzoffer;

/*
* 判断平衡二叉树 利用后序遍历
* */
public class BalancedTree2 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(21);
        TreeNode t3 = new TreeNode(31);
        TreeNode t4 = new TreeNode(41);
        t1.left = t2;
        t2.right = t3;
        t3.left = t4;
        System.out.println(isBalancedTree(t1));
    }

    public static boolean isBalancedTree(TreeNode root){
        return getDepth(root) != - 1;
    }

    // 利用后序遍历
    private static int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getDepth(root.left);
        if(left == -1){
            return -1;
        }
        int right = getDepth(root.right);
        if(right == -1){
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 :Math.abs(left - right) + 1;
    }


}
